/*
 * @lc app=leetcode.cn id=877 lang=typescript
 *
 * [877] 石子游戏
 */

// @lc code=start
function stoneGame(piles: number[]): boolean {
  const size = piles.length;
  // dp[i][j]表示此区间内双方石子数量的最大差值
  const dp = new Array(size).fill(0).map(() => new Array(size).fill(0));

  for (let i = 0; i < size; i++) {
    dp[i][i] = piles[i];
  }

  // 我们要求的结果是dp[0][size-1]，所以这里需要逆序遍历
  for (let i = size - 2; i >= 0; i--) {
    for (let j = i + 1; j < size; j++) {
      dp[i][j] = Math.max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
    }
  }

  return dp[0][size - 1] > 0;
}
// @lc code=end
